//给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 
//queries[i] = [xi, yi] 。 
//
// 对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1
//[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。 
//
// 返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。 
//
// 
//
// 示例 1： 
//
// 输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
//输出：[6,10,7]
//解释：
//对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。
//nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
//对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。
//nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
//对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。
//nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。
//因此，我们返回 [6,10,7] 。
// 
//
// 示例 2： 
//
// 输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
//输出：[9,9,9]
//解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。
// 
//
// 示例 3： 
//
// 输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
//输出：[-1]
//解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不
//存在答案。 
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == nums2.length 
// n == nums1.length 
// 1 <= n <= 10⁵ 
// 1 <= nums1[i], nums2[i] <= 10⁹ 
// 1 <= queries.length <= 10⁵ 
// queries[i].length == 2 
// xi == queries[i][1] 
// yi == queries[i][2] 
// 1 <= xi, yi <= 10⁹ 
// 
//
// Related Topics 栈 树状数组 线段树 数组 二分查找 排序 单调栈 👍 46 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-11-17 10:34:00
 * @description 2736.最大和查询
 */
public class MaximumSumQueries{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MaximumSumQueries().new Solution();
		 solution.maximumSumQueries(new int[]{2,1},new int[]{2,3},new int[][]{{3,3}});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //二维偏序问题
		 //超时
    public int[] maximumSumQueries1(int[] nums1, int[] nums2, int[][] queries) {
		int n = nums1.length;
		//保存和
		int [] sum=new int [n];
		//保存结果
		Map<String,Integer> t=new HashMap<>();
		int [] res=new int[queries.length];
		int max1 = Arrays.stream(nums1).max().getAsInt();
		int max2 = Arrays.stream(nums2).max().getAsInt();
		for (int i = 0; i < n; i++) {
			sum[i]=nums1[i]+nums2[i];
		}
		for (int i = 0; i < queries.length; i++) {
			if(t.containsKey(queries[i][0]+" "+queries[i][1])){
				res[i]=t.get(queries[i][0]+" "+queries[i][1]);
			}else {
				if(queries[i][0]>max1||queries[i][1]>max2){
					res[i]=-1;
				} else {
					int query=-1;
					for (int j = 0; j < n; j++) {
						int xi = queries[i][0];
						int yi = queries[i][1];
						if(nums1[j]>=xi&&nums2[j]>=yi){
								query=Math.max(query,sum[j]);
						}
					}
					res[i]=query;
					t.put(queries[i][0]+" "+queries[i][1],res[i]);
				}
			}
		}
		return  res;
	}

	public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
		int n=nums1.length;
		int [][] a=new int[n][2];
		//先把两个数组保存到一个数组里
		for (int i = 0; i < n; i++) {
			a[i][0]=nums1[i];
			a[i][1]=nums2[i];
		}
		//按照num1降序排序
		Arrays.sort(a,(o1,o2)->o2[0]-o1[0]);
		Integer [] qid=new Integer[queries.length];
		for (int i = 0; i < queries.length; i++) {
			qid[i]=i;
		}
		//将query也按照x的从大到小排列
		Arrays.sort(qid,((o1, o2) -> queries[o2][0]-queries[o1][0]));

		int[] res=new int[queries.length];
		//st维护当前满足条件的元素
		List<int[]> st=new ArrayList<>();
		int j=0;
		for (int i : qid) {
			int x=queries[i][0],y=queries[i][1];
			//nums1和queryx都是降序排序，所以下面只关心a[j][1]
			for(;j<n&&a[j][0]>=x;j++){
				// a[j][1] >= st.get(st.size()-1)[0]
				//如果nums2比之前的nums2小或者相等，就不考虑，
				//如果比之前的大，就把nums入栈，并且把栈顶弹出
				//最终得到一个栈：
				//nums2递增，nums1+nums2递减
				//在单调栈中二分>=y的最小的nums2j，得到的num1+num2就是最大的
				//因为num1是降序的，当前和比栈顶大，说明num2大于栈顶的num2,出栈后后面一定会入栈
				while (!st.isEmpty()&&st.get(st.size()-1)[1]<=a[j][0]+a[j][1]){
					st.remove(st.size()-1);
				}
				if(st.isEmpty()||st.get(st.size()-1)[0]<a[j][1]){
					st.add(new int[]{a[j][1],a[j][0]+a[j][1]});
				}
			}
			//每次二分时，st中的x，y都是满足条件的
			int p=lowerBound(st,y);
			res[i]=p<st.size()?st.get(p)[1]:-1;
		}
		return res;
	}
		//二分找到>=y的最小，开区间写法
	private int lowerBound(List<int []> st,int target){
		int l=-1,r=st.size();
		while (l+1<r){
			int m=(l+r)>>>1;
			if(st.get(m)[0]>=target){
				r=m;
			}else {
				l=m;
			}
		}
		return r;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
